package leetcode.doublepointer;


import leetcode.doublepointer.ListNode;

import java.util.Stack;

//21. 合并两个有序链表
//206. 反转链表
public class MergeTwoLists {

    // 合并两个有序链表
    //双指针
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode t1 = l1;
        ListNode t2 = l2;
        ListNode newList = new ListNode(0);
        ListNode temp = newList;
        while (t1 != null && t2 != null) {
            if (t1.val < t2.val) {
                temp.next = t1;
                temp = temp.next;
                t1 = t1.next;
            } else {
                temp.next = t2;
                temp = temp.next;
                t2 = t2.next;
            }
        }
        while (t1 != null) {
            temp.next = t1;
            temp = temp.next;
            t1 = t1.next;
        }
        while (t2 != null) {
            temp.next = t2;
            temp = temp.next;
            t2 = t2.next;
        }
        return newList.next;
    }

    //递归
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists2(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists2(l1, l2.next);
            return l2;
        }
    }

    //反转单链表----他这题只是值反转了，链表的指向没变
    //故,用栈
    public ListNode reverseList(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode p = head;
        while (p != null) {
            stack.push(p.val);
            p = p.next;

        }
        ListNode q = head;
        while (q != null) {
            q.val = stack.pop();
            q = q.next;
        }
        return head;
    }

    //通用的，把链表指向也改
    public ListNode reverseList2(ListNode head) {
        ListNode newList = new ListNode(0);
        ListNode temp = head;
        ListNode next = null;  //定义一个指针负责作为移动temp指针的临时变量
        while (temp!=null){
            //语句顺序不能变
            next = temp.next;
            temp.next = newList.next;
            newList.next = temp;
            temp = next;
        }
        return newList.next;
    }

}
